package slidewindow.窗口长度可变的滑动窗口题目;


// https://binarysearch.com/problems/Number-of-Operations-to-Decrement-Target-to-Zero
// 给你一个正整数数组nums和一个整数target。每一次操作，可以只能从nums数组的最前面或最后面删除一个数字v，同时将target减去v。 返回将target减为零所需的最少操作次数。如果不可能做到，则返回-1
class 删除数组头或尾使得删除的和为target_求最小删除次数_重做版 {
            public int solve(int[] nums, int target) {
                int sum  = 0;
                for(int num : nums) sum += num;
                target = sum - target;  // 转化为  求滑动窗口和为 sum - target  的最长长度
                if(target == 0) return nums.length;
                int l = 0, r = 0, maxLength = 0, sumInWindow = 0;
                // 双指针法  右指针右移  满足条件时左指针右移压缩窗口大小
                while(r < nums.length) {  
                    sumInWindow += nums[r];
                    while(l <= r && sumInWindow >= target){ 
                        if(sumInWindow == target) maxLength = Math.max(maxLength, r - l + 1);
                        sumInWindow -= nums[l];
                        l++;
                    }
                    r ++;
                }
                return maxLength == 0 ? -1 : nums.length - maxLength;
            }
        }
/**
 * 给你一个数组，你只可以移除数组两端的数。求最小移除次数，使得移除的数字和为 target。
 *
 * 我们可以反向思考，删除和为 target 的若干数字等价于保留若干和为 sum(A) - target 的数。
 * 这样问题就转化为求连续子数组和为 sum(A) - target 的最短子数组。这种问题可以使用滑动窗口来解决。
 */
public class 和为target的最小移除次数_x {
    public int findMinRemoveCount(int [] arr, int target) {
        int targetSum =0, windowSum = 0,
                moveCount = arr.length + 1,
                l = 0, r = 0;
        for(int item : arr) {
            targetSum += item;
        }
        targetSum -= target;
        while(r< arr.length){
            windowSum += arr[r++];
            while(windowSum >= targetSum && l < r) {
                if(windowSum == targetSum) {
                    moveCount = Math.min(moveCount, arr.length -r + l -1);
                }
                windowSum -= arr[l++];
            }
        }
        return moveCount;
    }
}
